ЗАДАЧИ НА ДЛИННУЮ АРИФМЕТИКУ
Шестаков Александр Петрович,
кафедра информатики Пермского государственного педагогического университета
Рассмотрим достаточно популярную в программировании задачу на работу с «длинными» числами. Реально с «астрономическими» или «микроскопическими» числами приходится сталкиваться не так уж и часто. Тем не менее, упражнения, рассматриваемые в этой публикации, могут послужить хорошей тренировкой в области программирования и занять достойное место в классах с углубленным изучением информатики или на кружках по программированию. Алгоритмы, представленные ниже, записаны на Turbo Pascal, версия 7.0. При желании или необходимости они могут легко быть адаптированы к любой другой программной среде.
Диапазон представления целых чисел (Integer, Word, LongInt) ограничен, о чем не раз уже говорилось (впрочем, для действительных величин это замечание тоже актуально). Поэтому при решении задач всегда приходится действовать с оглядкой, — как бы не допустить возникновения ошибки выхода за диапазон или переполнения. Например, вычисляя факториал (n!=123n), в диапазоне представления величин типа Integer удастся правильно получить только 7!=5040, а в диапазоне представления типа LongInt — 12!= 479001600. Для больших значений, конечно, можно использовать действительные типы данных, но это уже не гарантирует точного результата. Поэтому полезно для получения точных значений при действиях с многозначными числами разработать другие способы представления таких чисел, алгоритмы выполнения арифметических и других операций, процедуры ввода и вывода результатов и т.д.
Покажем реализацию решения такого рода задач на примере умножения одного многозначного числа на другое. Именно эта арифметическая операция наиболее часто используется при решении других задач.
Наиболее естественным способом представления многозначного числа является запись каждого его разряда в виде отдельного элемента линейного массива (или списка, где память под цифру будет отводиться по мере надобности, в то время как в массиве приходится заранее задавать максимальное количество элементов в нем). Пусть (для удобства дальнейших действий) разряды «длинного» числа при записи в массив нумеруются с единицы, начиная с разряда единиц, т.е. цифра из разряда единиц — элемент массива с номером один, цифра из разряда десятков — элемент массива с номером два и т.д. Определим для работы с «длинными» неотрицательными числами тип данных:
Const MNax = 2000;
Type Digit = 0..9;
DlChislo = Array[1..Nmax] Of Digit;
Для решения поставленной задачи необходимо уметь выполнять следующие действия:
1) ввод «длинного» числа;
2) собственно умножение двух «длинных» чисел;
3) вывод «длинного» числа;
4) определение количества цифр в записи числа.
Каждую из подзадач реализуем в виде отдельной подпрограммы. Начнем с ввода. Ввести большое число целесообразно в виде строки, а в дальнейшем преобразовать в массив цифр. В процедуре учтен указанный выше способ размещения «длинного» числа в массиве, т.е. с точки зрения пользователя число записывается как бы в обратном порядке.
{Процедура преобразования длинного числа, записанного в виде строки, в массив цифр; переменная OK принимает значение True, если в записи числа нет посторонних символов, отличных от десятичных цифр, иначе — false}
Procedure Translate(S : String; Var A : DlChislo; Var OK : Boolean);
Var I : Word;
Begin
Zero(A); I := Length(S); OK := True;
While (I >= 1) And OK Do
Begin If S[I] In [‘0’..’9’] Then A[Length(S) - I+ 1] := Ord(S[I]) - 48 Else OK := False; I := I - 1 End
End;
В процедуре вызывается подпрограмма Zero(A), назначение которой — запись нуля в каждый разряд длинного числа. Вот текст этой процедуры:
{Процедура обнуления длинного числа}
Procedure Zero(Var A : DlChislo);
Var I : Integer;
Begin
For I := 1 To NMax Do A[I] := 0;
End;
Таким образом, длинное число записано в массив, где впереди (в качестве элементов с большими номерами) стоят незначащие нули. При выполнени...
